\subsubsection{Solución elegida}



\subsubsection{Demostración}

Sea $\mathcal{S}$ = $\sum\limits$$_{j=1}^m t_{j}$$\sum\limits$$_{i=j}^m d_{i}$ mi secuencia que menor perdida da en la construccion de joyas segun el orden indicado anteriormente.
Sea $\mathcal{S}$$_1$ = $\sum\limits$$_{j=1}^m t_{j}$$\sum\limits$$_{i=j}^m d_{i}$, otra secuencia optima al igual que $\mathcal{S}$, tal que en al menos 2 elementos no se respetan la relacion de orden propuesta, esto quiere decir que existe un k y un j(  k, j $\in$ N, k+j $<$ n ) tal que $\frac{d_{k+j}}{t_{ik+j}}$ $>$ $\frac{d_{k}}{t_{k}}$.  

En particular veamos que si por lo menos dos elementos consecutivos, k y k+1 siendo k $\in$ N y 1 $\ge$ k $\ge$ n-1, no respetan el orden y por lo tanto esta secuencia tiene que ser mayor en cuanto a costo.\newline

Supongamos que no es menor el costo y por lo tanto.
\begin{center}
$\mathcal{S}$$_1$ $<$ $\mathcal{S}$
 $\iff$ $\sum\limits$$_{l=1}^n t_{l}$$_\mathcal{S}$$_1$$\sum\limits$$_{m=l}^n d_{m}$$_\mathcal{S}$$_1$ $<$ $\sum\limits$$_{j=1}^m t_{j}$$_\mathcal{S}$$\sum\limits$$_{i=j}^m d_{i}$$_\mathcal{S}$\newline
\end{center}

Es igual que  

\begin{center}
$\sum\limits$$_{l=1}^{k-1} t_{l}$$_\mathcal{S}$$_1$$\sum\limits$$_{m=l}^n d_{m}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k}^n d_{m}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ $\sum\limits$$_{m=k+1}^n d_{m}$$_\mathcal{S}$$_1$  +  $\sum\limits$$_{l=k+2}^n t_{l}$$_\mathcal{S}$$_1$$\sum\limits$$_{m=l}^n d_{m}$$_\mathcal{S}$$_1$ $<$ $\sum\limits$$_{j=1}^{k-1} t_{j}$$_\mathcal{S}$$\sum\limits$$_{i=j}^m d_{i}$$_\mathcal{S}$ + $t_{k}$$_\mathcal{S}$ * $\sum\limits$$_{i=k}^m d_{i}$$_\mathcal{S}$ + $t_{k+1}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+1}^m d_{i}$$_\mathcal{S}$  + $\sum\limits$$_{j=k+2}^m t_{j}$$_\mathcal{S}$$\sum\limits$$_{i=j}^m d_{i}$$_\mathcal{S}$
\end{center}

\newpage
Pero sabemos que los elementos de las secuencias son los mismos excepto los que se intercambiaron de lugar, en este caso el k y el k+1. \newline

a)
$\sum\limits$$_{l=1}^{k-1} t_{l}$$_\mathcal{S}$$_1$$\sum\limits$$_{m=l}^n d_{m}$$_\mathcal{S}$$_1$ = $\sum\limits$$_{j=1}^{k-1} t_{j}$$_\mathcal{S}$$\sum\limits$$_{i=j}^m d_{i}$$_\mathcal{S}$ \newline

b)
$\sum\limits$$_{l=k+2}^n t_{l}$$_\mathcal{S}$$_1$$\sum\limits$$_{m=l}^n d_{m}$$_\mathcal{S}$$_1$ = $\sum\limits$$_{j=k+2}^m t_{j}$$_\mathcal{S}$$\sum\limits$$_{i=j}^m d_{i}$$_\mathcal{S}$
\newline

Ya que al intercambiar los elementos k y k+1 no afectan en los costos de las construcciones de las otras joyas, solo afecta en los costos de las construcciones de ellas. Esto quiere decir que en el caso a) como las joyas no se construyeron suman por igual en las construcciones de las joyas 1 a k-1 y en el caso de las joyas k+2 a n como ya se construyeron no suman ningun costo.
Por lo tanto podemos cancelar los terminos en ambos lados de la desigualdad y nos queda

 $t_{k}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k}^n d_{m}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+1}^n d_{m}$$_\mathcal{S}$$_1$ 
$<$
$t_{k}$$_\mathcal{S}$ * $\sum\limits$$_{i=k}^m d_{i}$$_\mathcal{S}$ + $t_{k+1}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+1}^m d_{i}$$_\mathcal{S}$

A su vez en cada una de las sumatorias puedo separar los elementos que me interesa comparar entre ambas secuencias para eliminar los que son iguales entre ambas en la desigualdad.\newline


En la secuencia $\mathcal{S}$

$t_{k}$$_\mathcal{S}$ * $\sum\limits$$_{i=k}^m d_{i}$$_\mathcal{S}$ + $t_{k+1}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+1}^m d_{i}$$_\mathcal{S}$ = \newline 
\hspace{2cm} $t_{k}$$_\mathcal{S}$ *$d_{k}$$_\mathcal{S}$  + $t_{k}$$_\mathcal{S}$ * $d_{k+1}$$_\mathcal{S}$ + $t_{k}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+2}^m d_{i}$$_\mathcal{S}$ +  $t_{k+1}$$_\mathcal{S}$ * $d_{k+1}$$_\mathcal{S}$ + $t_{k+1}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+2}^m d_{i}$$_\mathcal{S}$
\newline

En la secuencia nos quedaria $\mathcal{S}$$_1$ 
\begin{center}
$t_{k}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k}^n d_{m}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+1}^n d_{m}$$_\mathcal{S}$$_1$ =  $t_{k}$$_\mathcal{S}$$_1$ * $d_{k}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$*$d_{k+1}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+2}^n d_{m}$$_\mathcal{S}$$_1$ +  $t_{k+1}$$_\mathcal{S}$$_1$ * $d_{k+1}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+2}^n d_{m}$$_\mathcal{S}$$_1$
\end{center}

A su vez por hipotesis sabemos que se intercambiaron los elementos k y k+1 , por lo tanto tenemos que
\begin{center}
$t_{k}$$_\mathcal{S}$ =  $t_{k+1}$$_\mathcal{S}$$_1$ y $t_{k+1}$$_\mathcal{S}$ = $t_{k}$$_\mathcal{S}$$_1$

$d_{k}$$_\mathcal{S}$ =  $d_{k+1}$$_\mathcal{S}$$_1$ y $d_{k+}$$_\mathcal{S}$ = $d_{k}$$_\mathcal{S}$$_1$
\end{center}

Reemplazando en la desigualdad nos quedaria
\begin{center}
$t_{k}$$_\mathcal{S}$$_1$ * $d_{k}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$*$d_{k+1}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+2}^n d_{m}$$_\mathcal{S}$$_1$ +$t_{k+1}$$_\mathcal{S}$$_1$ * $d_{k+1}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{m=k+2}^n d_{m}$$_\mathcal{S}$$_1$ $<$  $t_{k+1}$$_\mathcal{S}$$_1$  *$d_{k+1}$$_\mathcal{S}$$_1$  + $t_{k+1}$$_\mathcal{S}$$_1$ * $d_{k}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$ * $\sum\limits$$_{i=k+2}^m d_{i}$$_\mathcal{S}$$_1$ +  $t_{k}$$_\mathcal{S}$$_1$ * $d_{k}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$ * $\sum\limits$$_{i=k+2}^m d_{i}$$_\mathcal{S}$
\end{center}
Ahora puedo cancelar los terminos que son iguales en ambos lados de la igualdad.\newline

Primer Paso - Cancelo las sumatorias

\begin{center}
$t_{k}$$_\mathcal{S}$$_1$*$d_{k}$$_\mathcal{S}$$_1$ + $t_{k}$$_\mathcal{S}$$_1$*$d_{k+1}$$_\mathcal{S}$$_1$ + $t_{k+1}$$_\mathcal{S}$$_1$*$d_{k+1}$$_\mathcal{S}$$_1$ $<$ $t_{k+1}$$_\mathcal{S}$$_1$*$d_{k+1}$$_\mathcal{S}$$_1$  + $t_{k+1}$$_\mathcal{S}$$_1$*$d_{k}$$_\mathcal{S}$$_1$ +  $t_{k}$$_\mathcal{S}$$_1$*$d_{k}$$_\mathcal{S}$$_1$
\end{center}
Segundo Paso - Cancelo los otros terminos iguales
\begin{center}
$t_{k}$$_\mathcal{S}$$_1$ $d_{k+1}$$_\mathcal{S}$$_1$ $<$ $t_{k+1}$$_\mathcal{S}$$_1$ * $d_{k}$$_\mathcal{S}$$_1$
\end{center}

Tercer Paso - como $t_{k}$ y $t_{k+1}$ enteros positivos paso dividiendo.

\begin{center}

$\frac{d_{k+1}}{t_{k+1}}$ $<$ $\frac{d_{k}}{t_{k}}$.
\end{center}

Absurdo, Ya que en S estan ordenados por el orden y esto no podria estar pasando.



\subsubsection{Pseudoc\'odigo}




